package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 72. 编辑距离
 * @date 2024/12/21 10:25
 */
public class E72 {

    /**
     * <h3>方法一：动态规划，二维数组</h3>
     *
     * @param word1 单词1
     * @param word2 单词2
     * @return 编辑距离
     */
    public int minDistance1(String word1, String word2) {
        // 1. 创建动态数组，要考虑空字符，所以要多出一行一列
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int n = charArray2.length + 1, m = charArray1.length + 1;
        int[][] dp = new int[n][m];
        // 2. 初始化第一行和第一列
        for (int j = 1; j < m; j++) dp[0][j] = j;
        for (int i = 1; i < n; i++) dp[i][0] = i;
        // 3. 遍历dp数组，计算dp[i][j]
        int replace, insert, delete; // 替换、插入、删除对应操作数
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 3.1 如果word1和word2对应字符相等，则把word1前面的所有字符转换为word2前面的所有字符
                if (charArray2[i - 1] == charArray1[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                    // 3.2 如果word1和word2对应字符不相等，则需要考虑替换、插入、删除操作，取最小代价
                else {
                    // 3.2.1 替换操作的代价，将word1当前字符替换为word2对应字符转换为对应字符相等的情况
                    replace = dp[i - 1][j - 1] + 1;
                    // 3.2.2 插入操作的代价，在word1当前字符后插入一个与word2当前字符相等的字符，转换为对应字符相等的情况
                    insert = dp[i - 1][j] + 1;
                    // 3.2.3 删除操作的代价，将当前字符删除，删除后的word1转换为word2
                    delete = dp[i][j - 1] + 1;
                    // 3.2.4 取最小代价
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        // 4. 返回dp数组最后一行最后一列的值，即为编辑距离
        return dp[n - 1][m - 1];
    }

    /**
     * <h3>方法二：动态规划，一维数组</h3>
     *
     * @param word1 单词1
     * @param word2 单词2
     * @return 编辑距离
     */
    public int minDistance2(String word1, String word2) {
        // 1. 创建动态数组，要考虑空字符，所以要多出一行一列
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int n = charArray2.length + 1, m = charArray1.length + 1;
        int[] dp = new int[m];
        // 2. 初始化第一列
        for (int j = 1; j < m; j++) dp[j] = j;
        // 3. 遍历dp数组，计算dp[i][j]
        int replace, insert, delete; // 替换、插入、删除对应操作数
        for (int i = 1; i < n; i++) {
            int leftUp = dp[0]; // 更改之前要保存leftUp
            dp[0] = i;
            for (int j = 1; j < m; j++) {
                int origin = dp[j]; // 原始的dp[j]
                // 3.1 如果word1和word2对应字符相等，则把word1前面的所有字符转换为word2前面的所有字符
                if (charArray2[i - 1] == charArray1[j - 1]) dp[j] = leftUp;
                    // 3.2 如果word1和word2对应字符不相等，则需要考虑替换、插入、删除操作，取最小代价
                else {
                    // 3.2.1 替换操作的代价，将word1当前字符替换为word2对应字符转换为对应字符相等的情况
                    replace = leftUp + 1;
                    // 3.2.2 插入操作的代价，在word1当前字符后插入一个与word2当前字符相等的字符，转换为对应字符相等的情况
                    insert = origin + 1;
                    // 3.2.3 删除操作的代价，将word1当前字符删除，删除后的word1转换为word2
                    delete = dp[j - 1] + 1;
                    // 3.2.4 取最小代价
                    dp[j] = Math.min(replace, Math.min(insert, delete));
                }
                leftUp = origin; // 更改之后要保存leftUp
            }
        }
        // 4. 返回dp数组最后一行最后一列的值，即为编辑距离
        return dp[m - 1];
    }
}
